/**
 * 43. 字符串相乘
 * https://leetcode.cn/problems/multiply-strings/description/
 */
class Solution {
    public String multiply(String num1, String num2) {
        StringBuffer ret = new StringBuffer();
        int n = num1.length(), m = num2.length();
        int[] tmp = new int[n + m - 1];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int x = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                tmp[i + j] += x;
            }
        }

        if(tmp[0] == 0) return "0";

        int x = 0, i = n + m - 1 - 1;
        while(i >= 0 || x != 0) {
            if(i >= 0) {
                int y = x + tmp[i];
                ret.append(y % 10);
                x = y / 10;
            }else {
                ret.append(x);
                x /= 10;
            }
            i--;
        }

        return ret.reverse().toString();
    }
}